Query optimization is central to the efficient operation of a modern relational database system. The query optimizer is typically invoked every time a new query enters the system. The optimizer identifies an efficient execution plan for the query, based on available database statistics and cost functions for the database operators. In commercial systems, great care has been taken to reduce the overhead of query optimization. However, the task of the optimizer is complex, and the join ordering problem alone has complexity that is exponential in the number of tables [13] (see Appendix A for a list of cited references). As a result, the cost of optimization itself may represent a significant fraction of the elapsed time between query submission and answer generation.
If identical queries are submitted, the database system can cache the optimizer's plan the first time, and avoid reoptimization for subsequent query invocations. The query processor merely has to check for syntactic identity of the query with the cached query. This idea can be generalized to queries with parameters. Constants in the query are replaced with “bind variables” to generate a query template, in which the bind variables are parameters. The query processor can then cache a plan for a query template rather than for a query. As a result, frequently-submitted queries that differ only in the constants can avoid the cost of query optimization. Oracles provides such a facility [1], as do DB2® [17] and Microsoft® SQL Server [10].
There is a potential problem with this approach. A single plan is chosen for all instances of a query template. This plan, while optimal in a particular region of the parameter space, may be sub-optimal in another region. Savings achieved by not invoking the query optimizer may be nullified by the choice of a sub-optimal execution plan. In fact, often the difference in cost between the optimizer's plan and the cached plan exceeds the optimization time.
Modern transaction processing systems are often required to handle thousands of transactions per second. Consider, for example, a web-based Online Transaction Processing (OLTP) application, such as an on-line book store described by the TPC-W benchmark [3]. The system executes canned queries that share a small number of pre-defined templates, such as queries generated by the same HTML form, but differ in parameter values. An interactive system is expected to complete query processing and return results to the user in a short amount of time, often less than a second. A single user's queries may exhibit locality in the values of the submitted parameters, in which case a single query execution plan may be good enough. However, this locality is lost when many users interact with the system at any given time. Therefore, to ensure that an optimal plan is chosen for every query invocation, every instance of the query must be optimized anew. Many of these queries involve joins of several database tables and are thus non-trivial to optimize. In this setting, query optimization performed for every query instance adds significant overhead in terms of the overall execution time and CPU utilization.
A number of Parametric Query Optimization solutions have been proposed. The solution proposed by Ioannidis [13] fails to scale in the number of parameters, and does not directly handle continuous attributes. Geometric solutions proposed by Hulgeri and Sudarshan [12] are impractical because of the exponential explosion in the number of parameters and because they do not perform well with a typical real-life workload having multiple categorical attributes or where the underlying data is highly skewed.
Thus, there exists a need to overcome at least one of the preceding deficiencies and limitations of the related art.